package q207;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 207. 课程表
 */
public class Solution {

    // 只要找到回路就不能完成
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int i = 0; i < prerequisites.length; i++) {
            if (map.containsKey(prerequisites[i][0])) {
                map.get(prerequisites[i][0]).add(prerequisites[i][1]);
            } else {
                Set<Integer> set = new HashSet<>();
                set.add(prerequisites[i][1]);
                map.put(prerequisites[i][0], set);
            }
        }
        // 记录可以完成的课程
        for (int i = 0; i < prerequisites.length; i++) {
            int t0 = prerequisites[i][0];
            int t1 = prerequisites[i][1];
            Set<Integer> used = new HashSet<>();
            if (!can(map, used, t0, t1)) return false;
        }

        return true;
    }

    public boolean can(Map<Integer, Set<Integer>> map,Set<Integer> used, int t0, int t1) {
        if(used.contains(t1)) {
            return false;
        }
        if (map.containsKey(t1)) {
            for (Integer tt : map.get(t1)) {
                used.add(t0);
                boolean is = can(map, used, t1, tt);
                used.remove(tt);
                if (!is) {
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
//        int[][] prerequisites = {{1,4},{2,4},{3,1},{3,2}};
//        int[][] prerequisites = {{2,1},{1,0}};
//        int[][] prerequisites = {{1,2},{2,3},{2,10},{3,4},{4,5},{4,11},{5,1}};
        int[][] prerequisites = {{1,0},{0,3},{0,2},{3,2},{2,5},{4,5},{5,6},{2,4}};
        System.out.println(solution.canFinish(5, prerequisites));
    }
}
